Asynchronous transfer mode (ATM) communication systems are designed to support high-speed, low-delay multiplexing and switching of voice, data, video and other types of user information traffic. An ATM system segments user traffic into fixed-length 53-byte cells. A 5-byte header in each cell typically includes a virtual channel identifier (VCI) and a virtual path identifier (VPI) associated with the corresponding cell. The VCI and VPI fields together identify a virtual connection (VC) which is established when a user requests a network connection in an ATM system. Additional details regarding these and other aspects of ATM systems can be found in the ATM Forum, "ATM User-Network Interface Specification," Version 3.1, September, 1994, and in Martin de Prycker, "Asynchronous Transfer Mode: Solution for Broadband ISDN, " Ellis Horwood, New York, 1993, both of which are incorporated by reference herein. The allocation of available transmission opportunities or slots to user traffic cells is generally referred to as cell scheduling.
One possible ATM cell scheduling technique could involve calculating for a given VC an ideal time at which the VC should be serviced by allocating a cell to that VC. An ATM scheduling system could then mark in a stored table, list or other type of schedule the fact that a given VC X is ready for scheduling at a time Y. Because one or more other active VCs may have previously requested servicing at time Y, such a cell scheduling system would typically require a two-dimensional list of scheduling requests in which one dimension is time and the other dimension is the list of VCs scheduled to be serviced at a given time.
A significant problem with such a two-dimensional cell schedule is that it makes it difficult for a scheduling system to determine when a particular VC should be scheduled for servicing due to the fact that the calculation can no longer be based on time alone. This is because there could be a back-up of arbitrary depth at any given scheduled time. As a result, a servicing processor may arrive late at successive scheduled times. VCs that are scheduled further out in time could have been scheduled earlier in time had the scheduling system been aware of the delays that would be encountered by the servicing processor. For example, the scheduling system could have scheduled a given VC earlier in time while maintaining the necessary elapsed time between successive cell transmission events if it were able to account for the delays. This two-dimensional scheduling technique results in inefficient scheduling and thus reduced system throughput.
Prior art ATM cell processors also suffer from a number of other drawbacks. For example, most available cell processors typically utilize either a hard-wired approach to provide increased throughput speed or a programmable approach which provides a high degree of flexibility but at the cost of reducing throughput speed. Another problem is that prior art cell processor approaches generally do not allow system designers to provide a common, reprogrammable architecture suitable for use in a wide variety of different ATM-based products. Other serious problems with prior art cell processing include the latency associated with accessing control information from static random access memory (SRAM) or other types of control or system memory, the scheduling of constant bit rate (CBR) traffic in the presence of variable bit rate (VBR) traffic, and the failure of the prior art devices to provide support for virtual path (VP) tunneling.
As is apparent from the above, there is a need for improved ATM cell scheduling, servicing and other processing techniques which avoid the above-noted problems of the prior art.